//
// Created by wangxiyue on 2019/8/16.
//
#include <stdio.h>

int fib1();

int fib2();

int fib3();

int fib4();

int main() {

    printf("fib1(6)=%d\n", fib1(6));
    printf("fib2(6)=%d\n", fib2(6));
    printf("fib3(6)=%d\n", fib3(6));
    printf("fib4(6)=%d\n", fib4(6));

    return 0;
}

/**
 * 斐波那契数列实现方案一
 * @param n 第n个数
 * @return n个数的值
 */
int fib1(int n) {

    if (n <= 0) {
        return 1;
    } else if (n == 1) {
        return 1;
    } else {
        return fib1(n - 1) + fib1(n - 2);
    }
}

/**
 * 斐波那契数列实现方案二
 * @param n 第n个数
 * @return n个数的值
 */
int fib2(int n) {

    if (n <= 1) {
        return 1;
    } else {
        return fib1(n - 1) + fib1(n - 2);
    }
    /// return n<=1?1:fib1(n - 1) + fib1(n - 2);
}

/**
 * 斐波那契数列实现方案三
 * @param n  第n个数
 * @return n个数的值
 */
int mem[100];

int fib3(int n) {
    if (n <= 0) {
        return 1;
    } else if (n == 1) {
        return 1;
    } else if (!mem[n]) {
        mem[n] = fib1(n - 1) + fib1(n - 2);
    }
    return mem[n];
}

/**
 * 斐波那契数列实现方案四
 * @param n  第n个数
 * @return n个数的值
 */
int fib4(int n) {
    int fib[n + 1];
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i <= n; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}